package com.usc.mock.utlil;

import lombok.Data;
import org.springframework.util.CollectionUtils;

import java.util.ArrayList;
import java.util.List;

public class DijkstraUtil {

    private List<LineInfo> routeList = new ArrayList<>(); //记录路径
    private List<LineInfo> waitingList = new ArrayList<>();//此轮候选的点
    private String current = null;
    private int length = 0;

    private void update(List<LineInfo> wl) {
        List<LineInfo> update = new ArrayList<>();
        for (LineInfo a : wl) {
            for (LineInfo b : wl) {
                if (a.getTo().equals(b.getTo()) && a.getDimension() < b.getDimension()) {
                    update.add(b);
                }
            }
        }
        for (LineInfo c : update) {
            wl.remove(c);
        }
    }

    private void Remove(List<LineInfo> coll, String nt) {
        List<LineInfo> move = new ArrayList<>();
        for (LineInfo a : coll) {
            if (nt.equals(a.getTo()))
                move.add(a);
        }
        for (LineInfo a : move) {
            if (coll.contains(a))
                coll.remove(a);
        }
    }

    private void linkrouteList(List<LineInfo> rt) {
        List<LineInfo> linkroute = new ArrayList<>();
        int last = rt.size() - 1;
        for (int i = rt.size() - 2; i > -1; i--) {
            if (!rt.get(last).getFrom().equals(rt.get(i).getTo())) {
                linkroute.add(rt.get(i));
            } else if (rt.get(last).getFrom().equals(rt.get(i).getTo())) {
                last = i;
            }
        }
        for (LineInfo a : linkroute) {
            rt.remove(a);
        }
    }

    private void toWait(List<LineInfo> lineInfoList, String nt) {
        Remove(lineInfoList, current);
        for (LineInfo a : lineInfoList) {
            if (nt.equals(a.getFrom())) {
                waitingList.add(new LineInfo(a.getId(), a.getFrom(), a.getTo(), a.getDimension() + length));
            }
        }
        for (LineInfo b : waitingList) {
            if (lineInfoList.contains(b)) {
                lineInfoList.remove(b);
            }
        }
        update(waitingList);
    }


    private boolean selectNext(List<LineInfo> wl) {
        if (wl.size() == 0) {
            System.out.println("done");
            return false;
        } else if (wl.size() == 1) {
            current = wl.get(0).getTo();
            length = wl.get(0).getDimension();
            routeList.add(routeList.size(), wl.get(0));
            wl.remove(wl.get(0));
        } else {
            LineInfo s = wl.get(0);
            for (LineInfo a : wl) {
                if (a.getDimension() < s.getDimension()) {
                    s = a;
                }
            }
            current = s.getTo();
            length = s.getDimension();
            routeList.add(routeList.size(), s);
            wl.remove(s);//将waiting list中的这一点删去
        }
        return true;
    }


    /**
     * 计算路线
     *
     * @param start        起始点
     * @param stop         终点
     * @param lineInfoList 数据列表
     * @return 返回规划路线
     */
    public List<LineInfo> routePlanning(String start, String stop, List<LineInfo> lineInfoList) {
        current = start;
        if (!CollectionUtils.isEmpty(lineInfoList)) {
            for (int i = 0; ; i++) {
                if (stop.equals(current)) {
                    break;
                }
                toWait(lineInfoList, current);
                if (selectNext(waitingList))
                    continue;
                else
                    break;
            }
            if (routeList.size() != 0 && routeList.get(routeList.size() - 1).getTo().equals(stop)) {
                linkrouteList(routeList);
                return routeList;
            } else {
                System.err.println("no fucking way");
            }
        }
        return null;
    }

    public static void main(String[] args) {
        DijkstraUtil dijkstraUtil = new DijkstraUtil();

        List<LineInfo> lineInfoAllList = new ArrayList<LineInfo>();
        lineInfoAllList.add(new LineInfo(1L, "1026", "2010", 20));
        lineInfoAllList.add(new LineInfo(2L, "2010", "20", 100));
        lineInfoAllList.add(new LineInfo(3L, "1020", "1021", 80));
        lineInfoAllList.add(new LineInfo(4L, "10", "1020", 200));
        lineInfoAllList.add(new LineInfo(5L, "10", "1010", 500));
        lineInfoAllList.add(new LineInfo(6L, "20", "10", 2000));
        lineInfoAllList.add(new LineInfo(7L, "1020", "1022", 20));

        List<LineInfo> list = dijkstraUtil.routePlanning("1026", "1021", lineInfoAllList);
        if (!CollectionUtils.isEmpty(list)) {
            System.out.print(list.get(0).getFrom() + " -> ");
            for (LineInfo a : list) {
                System.out.print(a.getTo() + " ");
            }
            System.out.print("total: " + list.get(list.size() - 1).getDimension());
        }
    }


}


